class Solution
{
public:
    bool validPartition(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> canBeValid(n, 0);
        if (nums[n - 2] == nums[n - 1])
        {
            canBeValid[n - 2] = 1;
        }
        if (n >= 3)
        {
            if (nums[n - 1] == nums[n - 2] && nums[n - 2] == nums[n - 3])
            {
                canBeValid[n - 3] = 1;
            }
            else if (nums[n - 1] == nums[n - 2] + 1 && nums[n - 2] == nums[n - 3] + 1)
            {
                canBeValid[n - 3] = 1;
            }
        }
        for (int i = n - 4; i >= 0; --i)
        {
            if (nums[i] == nums[i + 1] && canBeValid[i + 2])
            {
                canBeValid[i] = 1;
            }
            else if (nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2] && canBeValid[i + 3])
            {
                canBeValid[i] = 1;
            }
            else if (nums[i] + 1 == nums[i + 1] && nums[i + 1] + 1 == nums[i + 2] && canBeValid[i + 3])
            {
                canBeValid[i] = 1;
            }
        }
        return canBeValid[0];
    }
};